main(n)
{
	scanf("%d",&n);
	printf("%d",(3L*n*n+5L*n+2)/2%45678);
}
